home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / langs / iconv8_s.arc / ICONX.ARC / RLARGINT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-28  |  47.7 KB  |  2,037 lines
  1. #include <math.h>
  2. #include "..\h\config.h"
  3. #include "..\h\rt.h"
  4. #include "rproto.h"
  5. #include <ctype.h>
  6.  
  7. #ifdef LargeInts
  8.  
  9. extern int over_flow;
  10.  
  11. /*
  12.  *  Conventions:
  13.  *
  14.  *  Bignums entering this module and leaving it are too large to
  15.  *  be represented with T_Integer.  So, externally, a given value
  16.  *  is always T_Integer or always T_Bignum.
  17.  *
  18.  *  Routines outside this module operate on bignums by calling
  19.  *  a routine like
  20.  *
  21.  *      bigadd(da, db, dx)
  22.  *
  23.  *  where da, db, and dx are pointers to tended descriptors.
  24.  *  For the common case where one argument is a T_Integer, these
  25.  *  call routines like
  26.  *
  27.  *      bigaddi(da, IntVal(*db), dx).
  28.  *
  29.  *  The bigxxxi routines can convert an integer to bignum form;
  30.  *  they use itobig.
  31.  *
  32.  *  The routines that actually do the work take (length, address)
  33.  *  pairs specifying unsigned base-B digit strings.  The sign handling
  34.  *  is done in the bigxxx routines.
  35.  */
  36.  
  37. /*
  38.  * Type for doing arithmetic on (2 * NB)-bit nonnegative numbers.
  39.  *  Normally unsigned but may be signed (with NB reduced appropriately)
  40.  *  if unsigned arithmetic is slow.
  41.  */
  42.  
  43. /* The bignum radix, B */
  44.  
  45. #define B            ((word)1 << NB)
  46.  
  47. /* Bignum digits in a word */
  48.  
  49. #define WORDLEN  (WordBits / NB + (WordBits % NB != 0))
  50.  
  51. /* size of a bignum block that will hold an integer */
  52.  
  53. #define INTBIGBLK  sizeof(struct b_bignum) + sizeof(DIGIT) * WORDLEN
  54.  
  55. /* lo(uword d) :            the low digit of a uword
  56.    hi(uword d) :            the rest, d is unsigned
  57.    signed_hi(uword d) :     the rest, d is signed
  58.    dbl(DIGIT a, DIGIT b) : the two-digit uword [a,b] */
  59.  
  60. #define lo(d)        ((d) & (B - 1))
  61. #define hi(d)        ((uword)(d) >> NB)
  62. #define dbl(a,b)     (((uword)(a) << NB) + (b))
  63.  
  64. #if ((-1) >> 1) < 0
  65. #define signed_hi(d) ((word)(d) >> NB)
  66. #else
  67. #define signbit      ((uword)1 << (WordBits - NB - 1))
  68. #define signed_hi(d) ((word)((((uword)(d) >> NB) ^ signbit) - signbit))
  69. #endif
  70.  
  71. /* BigNum(dptr dp) : the struct b_bignum pointed to by dp */
  72.  
  73. #define BigNum(dp)   ((struct b_bignum *)&BlkLoc(*dp)->bignumblk)
  74.  
  75. /* LEN(struct b_bignum *b) : number of significant digits */
  76.  
  77. #define LEN(b)       ((b)->lsd - (b)->msd + 1)
  78.  
  79. /* DIG(struct b_bignum *b, word i): pointer to ith most significant digit */
  80.  
  81. #define DIG(b,i)     (&(b)->digits[(b)->msd+(i)])
  82.  
  83. /* ceil, ln: ceil may be 1 too high in case ln is inaccurate */
  84.  
  85. #undef ceil
  86. #define ceil(x)      ((word)((x) + 1.01))
  87. #define ln(n)        (log((double)n))
  88.  
  89. /* determine the number of words needed for a bignum block with n digits */
  90.  
  91. #define BigNeed(n)   ( ((sizeof(struct b_bignum) + ((n) - 1) * sizeof(DIGIT)) \
  92.                + WordSize - 1) & -WordSize )
  93.  
  94. /* copied from rconv.c */
  95.  
  96. #if !EBCDIC
  97. #define tonum(c)     (isdigit(c) ? (c)-'0' : 10+(((c)|(040))-'a'))
  98. #else                    /* !EBCDIC */
  99. int tonum(c)
  100. int c;
  101. {
  102. #ifdef SASC
  103.    const static char *alphanum = "0123456789abcdefghijklmnopqrstuvwxyz" ;
  104.    char *where;
  105.  
  106.    where = memchr(alphanum, tolower(c), 36);
  107.    if (where == 0) return -1;
  108.    return where - alphanum;
  109. #else                    /* SASC */
  110.    if(isdigit(c)) return (c - '0');
  111.    if( (c | ' ') >= 'A' & (c | ' ') <= 'I') return( c - 'A' );
  112.    if( (c | ' ') >= 'J' & (c | ' ') <= 'R') return( (c - 'J') + 9 );
  113.    if( (c | ' ') >= 'S' & (c | ' ') <= 'Z') return( (c - 'S') + 18 );
  114.    return 0;
  115. #endif                    /* SASC */
  116.    }
  117. #endif                    /* !EBCDIC */
  118.  
  119. /* copied from oref.c */
  120.  
  121. #define RandVal (RanScale*(k_random=(RandA*(long)k_random+RandC)&0x7fffffffL))
  122.  
  123.  
  124. hidden int mkdesc    Params((struct b_bignum *x, dptr dx));
  125. hidden novalue itobig    Params((word i, struct b_bignum *x, dptr dx));
  126.  
  127. hidden novalue decout    Params((FILE *f, DIGIT *n, word l));
  128.  
  129. hidden int bigaddi    Params((dptr da, word i, dptr dx));
  130. hidden int bigsubi    Params((dptr da, word i, dptr dx));
  131. hidden int bigmuli    Params((dptr da, word i, dptr dx));
  132. hidden int bigdivi    Params((dptr da, word i, dptr dx));
  133. hidden int bigmodi    Params((dptr da, word i, dptr dx));
  134. hidden int bigpowi    Params((dptr da, word i, dptr dx));
  135. hidden int bigpowii    Params((word a, word i, dptr dx));
  136. hidden word bigcmpi    Params((dptr da, word i));
  137.  
  138. hidden DIGIT add1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n));
  139. hidden word sub1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n));
  140. hidden novalue mul1    Params((DIGIT *u, DIGIT *v, DIGIT *w, word n, word m));
  141. hidden novalue div1    
  142.         Params((DIGIT *a, DIGIT *b, DIGIT *q, DIGIT *r, word m, word n));
  143. hidden novalue compl1    Params((DIGIT *u, DIGIT *w, word n));
  144. hidden word cmp1    Params((DIGIT *u, DIGIT *v, word n));
  145. hidden DIGIT addi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  146. hidden novalue subi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  147. hidden DIGIT muli1    Params((DIGIT *u, word k, int c, DIGIT *w, word n));
  148. hidden DIGIT divi1    Params((DIGIT *u, word k, DIGIT *w, word n));
  149. hidden DIGIT shifti1    Params((DIGIT *u, word k, DIGIT c, DIGIT *w, word n));
  150. hidden word cmpi1    Params((DIGIT *u, word k, word n));
  151.  
  152. hidden novalue bdzero    Params((DIGIT *dest, word l));
  153. hidden novalue bdcopy    Params((DIGIT *src, DIGIT *dest, word l));
  154.  
  155. /*
  156.  * mkdesc -- put value into a descriptor
  157.  */
  158.  
  159. static int mkdesc(x, dx)
  160. struct b_bignum *x;
  161. dptr dx;
  162. {
  163.    word xlen, cmp;
  164.    static DIGIT maxword[WORDLEN] = { 1 << ((WordBits - 1) % NB) };
  165.  
  166.    /* suppress leading zero digits */
  167.  
  168.    while (x->msd != x->lsd && *DIG(x,0) == 0)
  169.       x->msd++;
  170.  
  171.    /* put it into a word if it fits, otherwise return the bignum */
  172.  
  173.    xlen = LEN(x);
  174.  
  175.    if (xlen < WORDLEN ||
  176.        (xlen == WORDLEN && ((cmp = cmp1(DIG(x,0), maxword, WORDLEN)) < 0 ||
  177.         (cmp == (word)0 && x->sign)))) {
  178.       word val = -(word)*DIG(x,0);
  179.       word i;
  180.  
  181.       for (i = x->msd; ++i <= x->lsd; )
  182.          val = (val << NB) - x->digits[i];
  183.       if (!x->sign)
  184.      val = -val;
  185.       dx->dword = D_Integer;
  186.       IntVal(*dx) = val;
  187.       }
  188.    else {
  189.       dx->dword = D_Bignum;
  190.       BlkLoc(*dx) = (union block *)x;
  191.       }
  192.    return Success;
  193. }
  194.  
  195. /*
  196.  *  i -> big
  197.  */
  198.  
  199. static novalue itobig(i, x, dx)
  200. word i;
  201. struct b_bignum *x;
  202. dptr dx;
  203. {
  204.    x->lsd = WORDLEN - 1;
  205.    x->msd = WORDLEN;
  206.    x->sign = 0;
  207.  
  208.    if (i == 0) {
  209.       x->msd--;
  210.       *DIG(x,0) = 0;
  211.       }
  212.    else if (i < 0) {
  213.       word d = lo(i);
  214.  
  215.       if (d != 0) {
  216.          d = B - d;
  217.          i += B;
  218.          }
  219.       i = - signed_hi(i);
  220.       x->msd--;
  221.       *DIG(x,0) = d;
  222.       x->sign = 1;
  223.       }
  224.             
  225.    while (i != 0) {
  226.       x->msd--;
  227.       *DIG(x,0) = lo(i);
  228.       i = hi(i);
  229.       }
  230.  
  231.    dx->dword = D_Bignum;
  232.    BlkLoc(*dx) = (union block *)x;
  233. }
  234.  
  235. /*
  236.  *  string -> bignum 
  237.  */
  238.  
  239. word bigradix(sign, r, s, dx)
  240. int sign;                      /* '-' or not */
  241. int r;                          /* radix 2 .. 36 */
  242. char *s;                        /* input string */
  243. dptr dx;                        /* output T_Integer or T_Bignum */
  244. {
  245.    struct b_bignum *b;
  246.    DIGIT *bd;
  247.    word len;
  248.    int c;
  249.  
  250.    if (r == 0)
  251.       return CvtFail;
  252.    len = ceil(strlen(s) * ln(r) / ln(B));
  253.    if (blkreq(BigNeed(len)) == Error)
  254.       return CvtFail;
  255.    b = alcbignum(len);
  256.    bd = DIG(b,0);
  257.  
  258.    bdzero(bd, len);
  259.  
  260.    if (r < 2 || r > 36)
  261.       return CvtFail;
  262.  
  263.    for (c = *s++; isalnum(c); c = *s++) {
  264.       c = tonum(c);
  265.       if (c >= r)
  266.      return CvtFail;
  267.       muli1(bd, (word)r, c, bd, len);
  268.       }
  269.  
  270.    while (isspace(c))
  271.       c = *s++;
  272.  
  273.    if (c != '\0')
  274.       return CvtFail;
  275.  
  276.    if (sign == '-')
  277.       b->sign = 1;
  278.  
  279.    /* put value into dx and return the type */
  280.  
  281.    (void)mkdesc(b, dx);
  282.    return Type(*dx);
  283. }
  284.  
  285. /*
  286.  *  bignum -> real
  287.  */
  288.  
  289. double bigtoreal(da)
  290. dptr da;
  291. {
  292.    word i;
  293.    double r = 0;
  294.    struct b_bignum *b = &BlkLoc(*da)->bignumblk;
  295.  
  296.    for (i = b->msd; i <= b->lsd; i++)
  297.       r = r * B + b->digits[i];
  298.  
  299.    return (b->sign ? -r : r);
  300. }
  301. /*
  302.  *  real -> bignum
  303.  */
  304.  
  305. int realtobig(da, dx)
  306. dptr da, dx;
  307. {
  308.    double x = BlkLoc(*da)->realblk.realval;
  309.    struct b_bignum *b;
  310.    word i, blen;
  311.    word d;
  312.  
  313.    if (x > 0.9999 * MinLong && x < 0.9999 * MaxLong) {
  314.       MakeInt((word)x, dx);
  315.       return Success;        /* got lucky; a simple integer suffices */
  316.       }
  317.  
  318.    x = x > 0 ? x : -x;
  319.    blen = ln(x) / ln(B) + 0.99;
  320.    for (i = 0; i < blen; i++)
  321.       x /= B;
  322.    if (x >= 1.0) {
  323.       x /= B;
  324.       blen += 1;
  325.       }
  326.  
  327.    if (blkreq(BigNeed(blen)) == Error)
  328.       return Error;
  329.    b = alcbignum(blen);
  330.    for (i = 0; i < blen; i++) {
  331.       d = (x *= B);
  332.       *DIG(b,i) = d;
  333.       x -= d;
  334.       }
  335.      
  336.    b->sign = x < 0;
  337.    return mkdesc(b, dx);
  338. }
  339.  
  340. /*
  341.  *  bignum -> string
  342.  */
  343.  
  344. int bigtos(da, dx)
  345. dptr da, dx;
  346. {
  347.    struct b_bignum *a, *temp;
  348.    word alen = LEN(BigNum(da));
  349.    word slen = ceil(alen * ln(B) / ln(10));
  350.    char *p, *q;
  351.  
  352.    if (strreq(slen) == Error || blkreq(BigNeed(alen)) == Error) 
  353.       return CvtFail;
  354.    a = BigNum(da);
  355.    temp = alcbignum(alen);
  356.    if (a->sign)
  357.       slen++;
  358.    q = alcstr("",slen);
  359.    bdcopy(DIG(a,0), DIG(temp,0), alen);
  360.    p = q += slen;
  361.    while (cmpi1(DIG(temp,0), (word)0, alen))
  362.       *--p = '0' + divi1(DIG(temp,0), (word)10, DIG(temp,0), alen);
  363.    if (a->sign)
  364.       *--p = '-';
  365.    StrLen(*dx) = q - p;
  366.    StrLoc(*dx) = p;
  367.    return Cvt;
  368. }
  369.  
  370. /*
  371.  *  bignum -> file 
  372.  */
  373.  
  374. novalue bigprint(f, da)
  375. FILE *f;
  376. dptr da;
  377. {
  378.    struct b_bignum *a, *temp;
  379.    word alen = LEN(BigNum(da));
  380.    word slen, dlen;
  381.  
  382.    slen = (BlkLoc(*da)->bignumblk.lsd - BlkLoc(*da)->bignumblk.msd + 1);
  383.    dlen = slen * NB * 0.3010299956639812;    /* 1 / log2(10) */
  384.    if (dlen > MaxDigits) {
  385.       fprintf(f, "integer(~%ld)",dlen - 2);    /* center estimate */
  386.       return;
  387.       }
  388.  
  389.    if (blkreq(BigNeed(alen)) == Error) {
  390.       fatalerr(0, NULL);        /* not worth passing this one back */
  391.       }
  392.    temp = alcbignum(alen);
  393.    a = BigNum(da);
  394.    bdcopy(DIG(a,0), DIG(temp,0), alen);
  395.    if (a->sign)
  396.       putc('-', f);
  397.    decout(f, DIG(temp,0), alen);
  398. }
  399.  
  400. static novalue decout(f, n, l)
  401. FILE *f;
  402. DIGIT *n;
  403. word l;
  404. {
  405.    word i = divi1(n, (word)10, n, l);
  406.  
  407.    if (cmpi1(n, (word)0, l))
  408.       decout(f, n, l);
  409.    putc('0' + i, f);
  410. }
  411.  
  412. /*
  413.  *  da -> dx
  414.  */
  415.  
  416. int cpbignum(da, dx)
  417. dptr da, dx;
  418. {
  419.    struct b_bignum *a;
  420.    word alen = LEN(BigNum(da));
  421.    struct b_bignum *x;
  422.  
  423.    if (blkreq(BigNeed(alen)) == Error)
  424.       return Error;
  425.    x = alcbignum(alen);
  426.    a = BigNum(da);
  427.    bdcopy(DIG(a,0), DIG(x,0), alen);
  428.    x->sign = a->sign;
  429.    return mkdesc(x, dx);
  430. }
  431.  
  432. /*
  433.  *  da + db -> dx
  434.  */
  435.  
  436. int bigadd(da, db, dx)
  437. dptr da, db;
  438. dptr dx;
  439. {
  440.    struct b_bignum *x, *a, *b;
  441.    word alen, blen;
  442.    word c;
  443.  
  444.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  445.       alen = LEN(BigNum(da));
  446.       blen = LEN(BigNum(db));
  447.       if (blkreq(BigNeed(alen > blen ? alen + 1 : blen + 1)) == Error)
  448.      return Error;
  449.       a = BigNum(da);
  450.       b = BigNum(db);
  451.       if (a->sign == b->sign) {
  452.          if (alen > blen) {
  453.             x = alcbignum(alen + 1);
  454.             c = add1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen+1), blen);
  455.             *DIG(x,0) = addi1(DIG(a,0), c, DIG(x,1), alen-blen);
  456.             }
  457.          else if (alen == blen) {
  458.             x = alcbignum(alen + 1);
  459.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  460.             }
  461.          else {
  462.             x = alcbignum(blen + 1);
  463.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  464.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  465.             }
  466.          x->sign = a->sign;
  467.          }
  468.       else {
  469.          if (alen > blen) {
  470.             x = alcbignum(alen);
  471.             c = sub1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen), blen);
  472.             subi1(DIG(a,0), -c, DIG(x,0), alen-blen);
  473.             x->sign = a->sign;
  474.             }
  475.          else if (alen == blen) {
  476.             x = alcbignum(alen);
  477.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  478.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  479.                x->sign = a->sign;
  480.                }
  481.             else {
  482.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  483.                x->sign = b->sign;
  484.                }
  485.             }
  486.          else {
  487.             x = alcbignum(blen);
  488.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  489.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  490.             x->sign = b->sign;
  491.             }
  492.          }
  493.       return mkdesc(x, dx);
  494.       }
  495.    else if (Type(*da) == T_Bignum)    /* bignum + integer */
  496.       return bigaddi(da, IntVal(*db), dx);
  497.    else if (Type(*db) == T_Bignum)    /* integer + bignum */
  498.       return bigaddi(db, IntVal(*da), dx);
  499.    else {                             /* integer + integer */
  500.       struct descrip td;
  501.       char tdigits[INTBIGBLK];
  502.  
  503.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  504.       return bigaddi(&td, IntVal(*db), dx);
  505.       }
  506. }
  507.  
  508. /*
  509.  *  da - db -> dx
  510.  */ 
  511.  
  512. int bigsub(da, db, dx)
  513. dptr da, db, dx;
  514. {
  515.    struct descrip td;
  516.    char tdigits[INTBIGBLK];
  517.    struct b_bignum *a, *b, *x;
  518.    word alen, blen;
  519.    word c;
  520.  
  521.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  522.       alen = LEN(BigNum(da));
  523.       blen = LEN(BigNum(db));
  524.       if (blkreq(BigNeed(alen > blen ? alen + 1 : blen + 1)) == Error)
  525.      return Error;
  526.       a = BigNum(da);
  527.       b = BigNum(db);
  528.       if (a->sign != b->sign) {
  529.          if (alen > blen) {
  530.             x = alcbignum(alen + 1);
  531.             c = add1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen+1), blen);
  532.             *DIG(x,0) = addi1(DIG(a,0), c, DIG(x,1), alen-blen);
  533.             }
  534.          else if (alen == blen) {
  535.             x = alcbignum(alen + 1);
  536.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  537.             }
  538.          else {
  539.             x = alcbignum(blen + 1);
  540.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  541.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  542.             }
  543.          x->sign = a->sign;
  544.          }
  545.       else {
  546.          if (alen > blen) {
  547.             x = alcbignum(alen);
  548.             c = sub1(DIG(a,alen-blen), DIG(b,0), DIG(x,alen-blen), blen);
  549.             subi1(DIG(a,0), -c, DIG(x,0), alen-blen);
  550.             x->sign = a->sign;
  551.             }
  552.          else if (alen == blen) {
  553.             x = alcbignum(alen);
  554.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  555.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  556.                x->sign = a->sign;
  557.                }
  558.             else {
  559.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  560.                x->sign = 1 ^ b->sign;
  561.                }
  562.             }
  563.          else {
  564.             x = alcbignum(blen);
  565.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  566.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  567.             x->sign = 1 ^ b->sign;
  568.             }
  569.          }
  570.       return mkdesc(x, dx);
  571.       }
  572.    else if (Type(*da) == T_Bignum)     /* bignum - integer */
  573.       return bigsubi(da, IntVal(*db), dx);
  574.    else if (Type(*db) == T_Bignum) {   /* integer - bignum */
  575.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  576.       alen = LEN(BigNum(&td));
  577.       blen = LEN(BigNum(db));
  578.       if (blkreq(BigNeed(alen > blen ? alen + 1 : blen + 1)) == Error)
  579.      return Error;
  580.       a = BigNum(&td);
  581.       b = BigNum(db);
  582.       if (a->sign != b->sign) {
  583.          if (alen == blen) {
  584.             x = alcbignum(alen + 1);
  585.             *DIG(x,0) = add1(DIG(a,0), DIG(b,0), DIG(x,1), alen);
  586.             }
  587.          else {
  588.             x = alcbignum(blen + 1);
  589.             c = add1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen+1), alen);
  590.             *DIG(x,0) = addi1(DIG(b,0), c, DIG(x,1), blen-alen);
  591.             }
  592.          x->sign = a->sign;
  593.          }
  594.       else {
  595.          if (alen == blen) {
  596.             x = alcbignum(alen);
  597.             if (cmp1(DIG(a,0), DIG(b,0), alen) > 0) {
  598.                (void)sub1(DIG(a,0), DIG(b,0), DIG(x,0), alen);
  599.                x->sign = a->sign;
  600.                }
  601.             else {
  602.                (void)sub1(DIG(b,0), DIG(a,0), DIG(x,0), alen);
  603.                x->sign = 1 ^ b->sign;
  604.                }
  605.             }
  606.          else {
  607.             x = alcbignum(blen);
  608.             c = sub1(DIG(b,blen-alen), DIG(a,0), DIG(x,blen-alen), alen);
  609.             subi1(DIG(b,0), -c, DIG(x,0), blen-alen);
  610.             x->sign = 1 ^ b->sign;
  611.             }
  612.          }
  613.       return mkdesc(x, dx);
  614.       }
  615.    else {                              /* integer - integer */
  616.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  617.       return bigsubi(&td, IntVal(*db), dx);
  618.       }
  619.       
  620. }
  621.  
  622. /*
  623.  *  da * db -> dx
  624.  */
  625.  
  626. int bigmul(da, db, dx)
  627. dptr da, db, dx;
  628. {
  629.    struct b_bignum *a, *b, *x;
  630.    word alen, blen;
  631.  
  632.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  633.       alen = LEN(BigNum(da));
  634.       blen = LEN(BigNum(db));
  635.       if (blkreq(BigNeed(alen + blen)) == Error)
  636.      return Error;
  637.       a = BigNum(da);
  638.       b = BigNum(db);
  639.       x = alcbignum(alen + blen);
  640.       mul1(DIG(a,0), DIG(b,0), DIG(x,0), alen, blen);
  641.       x->sign = a->sign ^ b->sign;
  642.       return mkdesc(x, dx);
  643.       }
  644.    else if (Type(*da) == T_Bignum)    /* bignum * integer */
  645.       return bigmuli(da, IntVal(*db), dx);
  646.    else if (Type(*db) == T_Bignum)    /* integer * bignum */
  647.       return bigmuli(db, IntVal(*da), dx);
  648.    else {                             /* integer * integer */
  649.       struct descrip td;
  650.       char tdigits[INTBIGBLK];
  651.  
  652.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  653.       return bigmuli(&td, IntVal(*db), dx);
  654.       }
  655. }
  656.  
  657. /*
  658.  *  da / db -> dx
  659.  */
  660.  
  661. int bigdiv(da, db, dx)
  662. dptr da, db, dx;
  663. {
  664.    struct b_bignum *a, *b, *x;
  665.    word alen, blen;
  666.  
  667.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  668.       alen = LEN(BigNum(da));
  669.       blen = LEN(BigNum(db));
  670.       if (alen < blen) {
  671.          MakeInt(0, dx);
  672.          return Success;
  673.          }
  674.       if (blkreq(BigNeed(alen-blen+1)+BigNeed(alen+1)+BigNeed(blen)) == Error)
  675.      return Error;
  676.       a = BigNum(da);
  677.       b = BigNum(db);
  678.       x = alcbignum(alen - blen + 1);
  679.       if (blen == 1)
  680.          divi1(DIG(a,0), (word)*DIG(b,0), DIG(x,0), alen);
  681.       else
  682.          div1(DIG(a,0), DIG(b,0), DIG(x,0), NULL, alen-blen, blen);
  683.       x->sign = a->sign ^ b->sign;
  684.       return mkdesc(x, dx);
  685.       }
  686.    else if (Type(*da) == T_Bignum)     /* bignum / integer */
  687.       return bigdivi(da, IntVal(*db), dx);
  688.    else if (Type(*db) == T_Bignum) {   /* integer / bignum */
  689.       MakeInt(0, dx);
  690.       return Success;
  691.       }
  692.    /* not called for integer / integer */
  693. }
  694.  
  695. /*
  696.  *  da % db -> dx
  697.  */
  698.  
  699. int bigmod(da, db, dx)
  700. dptr da, db, dx;
  701. {
  702.    struct b_bignum *a, *b, *x, *temp;
  703.    word alen, blen;
  704.  
  705.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  706.       alen = LEN(BigNum(da));
  707.       blen = LEN(BigNum(db));
  708.       if (alen < blen) {
  709.          cpbignum(da, dx);
  710.          return Success;
  711.          }
  712.       if (blkreq(BigNeed(blen)+BigNeed(alen+1)+BigNeed(blen)) == Error)
  713.      return Error;
  714.       a = BigNum(da);
  715.       b = BigNum(db);
  716.       x = alcbignum(blen);
  717.       if (blen == 1) {
  718.      temp = alcbignum(alen);
  719.          *DIG(x,0) = divi1(DIG(a,0), (word)*DIG(b,0), DIG(temp,0), alen);
  720.          }
  721.       else
  722.          div1(DIG(a,0), DIG(b,0), NULL, DIG(x,0), alen-blen, blen);
  723.       x->sign = a->sign;
  724.       return mkdesc(x, dx);
  725.       }
  726.    else if (Type(*da) == T_Bignum)     /* bignum % integer */
  727.       return bigmodi(da, IntVal(*db), dx);
  728.    else if (Type(*db) == T_Bignum) {   /* integer % bignum */
  729.       struct descrip td;
  730.       char tdigits[INTBIGBLK];
  731.  
  732.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  733.       cpbignum(&td, dx);
  734.       return Success;
  735.       }
  736.    /* not called for integer % integer */
  737. }
  738.  
  739. /*
  740.  *  -i -> dx
  741.  */
  742.  
  743. int bigneg(da, dx)
  744. dptr da, dx;
  745. {
  746.    struct descrip td;
  747.    char tdigits[INTBIGBLK];
  748.  
  749.    itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  750.    BigNum(&td)->sign ^= 1;
  751.    return cpbignum(&td, dx);
  752. }
  753.  
  754. /*
  755.  *  da ^ db -> dx
  756.  */
  757.  
  758. int bigpow(da, db, dx)
  759. dptr da, db, dx;
  760. {
  761.    word n;
  762.  
  763.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  764.       if (BigNum(db)->sign) {
  765.          MakeInt(0, dx);
  766.          }
  767.       else {
  768.          n = LEN(BigNum(db)) * NB;
  769.          /* scan bits left to right.  skip leading 1. */
  770.          while (--n >= 0)
  771.             if ((*DIG(BigNum(db), n / NB) & (1 << (n % NB))))
  772.                break;
  773.          /* then, for each zero, square the partial result;
  774.           *  for each one, square it and multiply it by a */
  775.          *dx = *da;
  776.          while (--n >= 0) {
  777.             if (bigmul(dx, dx, dx) == Error)
  778.            return Error;
  779.             if ((*DIG(BigNum(db), n / NB) & (1 << (n % NB))))
  780.                if (bigmul(dx, da, dx) == Error)
  781.           return Error;
  782.         }
  783.          }
  784.       return Success;
  785.       }
  786.    else if (Type(*da) == T_Bignum)    /* bignum ^ integer */
  787.       return bigpowi(da, IntVal(*db), dx);
  788.    else if (Type(*db) == T_Bignum)    /* integer ^ bignum */
  789.       return bigpowii(IntVal(*da), (word)bigtoreal(db), dx);
  790.    else                               /* integer ^ integer */
  791.       return bigpowii(IntVal(*da), IntVal(*db), dx);
  792. }
  793.  
  794. /*
  795.  *  iand(da, db) -> dx
  796.  */
  797.  
  798. int bigand(da, db, dx)
  799. dptr da, db, dx;
  800. {
  801.    struct b_bignum *a, *b, *x;
  802.    word alen, blen, xlen;
  803.    word i;
  804.    struct b_bignum *tad, *tbd;
  805.    DIGIT *ad, *bd;
  806.    struct descrip td;
  807.    char tdigits[INTBIGBLK];
  808.  
  809.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  810.       alen = LEN(BigNum(da));
  811.       blen = LEN(BigNum(db));
  812.       xlen = alen > blen ? alen : blen;
  813.       if (blkreq(3 * BigNeed(xlen)) == Error)
  814.          return Error;
  815.       a = BigNum(da);
  816.       b = BigNum(db);
  817.       x = alcbignum(xlen);
  818.  
  819.       if (alen == xlen && !a->sign)
  820.          ad = DIG(a,0);
  821.       else {
  822.          tad = alcbignum(xlen);
  823.          ad = DIG(tad,0);
  824.          bdzero(ad, xlen - alen);
  825.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  826.          if (a->sign)
  827.         compl1(ad, ad, xlen);
  828.          }
  829.  
  830.       if (blen == xlen && !b->sign)
  831.          bd = DIG(b,0);
  832.       else {
  833.          tbd = alcbignum(xlen);
  834.          bd = DIG(tbd,0);
  835.          bdzero(bd, xlen - blen);
  836.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  837.          if (b->sign)
  838.         compl1(bd, bd, xlen);
  839.          }
  840.         
  841.       for (i = 0; i < xlen; i++)
  842.          *DIG(x,i) = ad[i] & bd[i];
  843.  
  844.       if (a->sign & b->sign) {
  845.          x->sign = 1;
  846.          compl1(DIG(x,0), DIG(x,0), xlen);
  847.          }
  848.       }
  849.    else if (Type(*da) == T_Bignum) {   /* iand(bignum,integer) */
  850.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  851.       alen = LEN(BigNum(da));
  852.       blen = LEN(BigNum(&td));
  853.       xlen = alen > blen ? alen : blen;
  854.       if (blkreq(3 * BigNeed(alen)) == Error)
  855.          return Error;
  856.       a = BigNum(da);
  857.       b = BigNum(&td);
  858.       x = alcbignum(alen);
  859.  
  860.       if (alen == xlen && !a->sign)
  861.          ad = DIG(a,0);
  862.       else {
  863.          tad = alcbignum(xlen);
  864.          ad = DIG(tad,0);
  865.          bdzero(ad, xlen - alen);
  866.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  867.          if (a->sign)
  868.         compl1(ad, ad, xlen);
  869.          }
  870.  
  871.       if (blen == xlen && !b->sign)
  872.          bd = DIG(b,0);
  873.       else {
  874.          tbd = alcbignum(xlen);
  875.          bd = DIG(tbd,0);
  876.          bdzero(bd, xlen - blen);
  877.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  878.          if (b->sign)
  879.         compl1(bd, bd, xlen);
  880.          }
  881.         
  882.       for (i = 0; i < xlen; i++)
  883.          *DIG(x,i) = ad[i] & bd[i];
  884.  
  885.       if (a->sign & b->sign) {
  886.          x->sign = 1;
  887.          compl1(DIG(x,0), DIG(x,0), xlen);
  888.          }
  889.       }
  890.    else if (Type(*db) == T_Bignum) {   /* iand(integer,bignum) */
  891.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  892.       alen = LEN(BigNum(&td));
  893.       blen = LEN(BigNum(db));
  894.       xlen = alen > blen ? alen : blen;
  895.       if (blkreq(3 * BigNeed(blen)) == Error)
  896.          return Error;
  897.       a = BigNum(&td);
  898.       b = BigNum(db);
  899.       x = alcbignum(blen);
  900.  
  901.       if (alen == xlen && !a->sign)
  902.          ad = DIG(a,0);
  903.       else {
  904.          tad = alcbignum(xlen);
  905.          ad = DIG(tad,0);
  906.          bdzero(ad, xlen - alen);
  907.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  908.          if (a->sign)
  909.         compl1(ad, ad, xlen);
  910.          }
  911.  
  912.       if (blen == xlen && !b->sign)
  913.          bd = DIG(b,0);
  914.       else {
  915.          tbd = alcbignum(xlen);
  916.          bd = DIG(tbd,0);
  917.          bdzero(bd, xlen - blen);
  918.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  919.          if (b->sign)
  920.         compl1(bd, bd, xlen);
  921.          }
  922.         
  923.       for (i = 0; i < xlen; i++)
  924.          *DIG(x,i) = ad[i] & bd[i];
  925.  
  926.       if (a->sign & b->sign) {
  927.          x->sign = 1;
  928.          compl1(DIG(x,0), DIG(x,0), xlen);
  929.          }
  930.       }
  931.    /* not called for iand(integer,integer) */
  932.  
  933.    return mkdesc(x, dx);
  934. }
  935.  
  936. /*
  937.  *  ior(da, db) -> dx
  938.  */
  939.  
  940. int bigor(da, db, dx)
  941. dptr da, db, dx;
  942. {
  943.    struct b_bignum *a, *b, *x;
  944.    word alen, blen, xlen;
  945.    word i;
  946.    struct b_bignum *tad, *tbd;
  947.    DIGIT *ad, *bd;
  948.    struct descrip td;
  949.    char tdigits[INTBIGBLK];
  950.  
  951.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  952.       alen = LEN(BigNum(da));
  953.       blen = LEN(BigNum(db));
  954.       xlen = alen > blen ? alen : blen;
  955.       if (blkreq(3 * BigNeed(xlen)) == Error)
  956.          return Error;
  957.       a = BigNum(da);
  958.       b = BigNum(db);
  959.       x = alcbignum(xlen);
  960.  
  961.       if (alen == xlen && !a->sign)
  962.          ad = DIG(a,0);
  963.       else {
  964.          tad = alcbignum(xlen);
  965.          ad = DIG(tad,0);
  966.          bdzero(ad, xlen - alen);
  967.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  968.          if (a->sign)
  969.         compl1(ad, ad, xlen);
  970.          }
  971.  
  972.       if (blen == xlen && !b->sign)
  973.          bd = DIG(b,0);
  974.       else {
  975.          tbd = alcbignum(xlen);
  976.          bd = DIG(tbd,0);
  977.          bdzero(bd, xlen - blen);
  978.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  979.          if (b->sign)
  980.         compl1(bd, bd, xlen);
  981.          }
  982.         
  983.       for (i = 0; i < xlen; i++)
  984.          *DIG(x,i) = ad[i] | bd[i];
  985.  
  986.       if (a->sign | b->sign) {
  987.          x->sign = 1;
  988.          compl1(DIG(x,0), DIG(x,0), xlen);
  989.          }
  990.       }
  991.    else if (Type(*da) == T_Bignum) {   /* ior(bignum,integer) */
  992.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  993.       alen = LEN(BigNum(da));
  994.       blen = LEN(BigNum(&td));
  995.       xlen = alen > blen ? alen : blen;
  996.       if (blkreq(3 * BigNeed(alen)) == Error)
  997.          return Error;
  998.       a = BigNum(da);
  999.       b = BigNum(&td);
  1000.       x = alcbignum(alen);
  1001.  
  1002.       if (alen == xlen && !a->sign)
  1003.          ad = DIG(a,0);
  1004.       else {
  1005.          tad = alcbignum(xlen);
  1006.          ad = DIG(tad,0);
  1007.          bdzero(ad, xlen - alen);
  1008.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1009.          if (a->sign)
  1010.         compl1(ad, ad, xlen);
  1011.          }
  1012.  
  1013.       if (blen == xlen && !b->sign)
  1014.          bd = DIG(b,0);
  1015.       else {
  1016.          tbd = alcbignum(xlen);
  1017.          bd = DIG(tbd,0);
  1018.          bdzero(bd, xlen - blen);
  1019.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1020.          if (b->sign)
  1021.         compl1(bd, bd, xlen);
  1022.          }
  1023.         
  1024.       for (i = 0; i < xlen; i++)
  1025.          *DIG(x,i) = ad[i] | bd[i];
  1026.  
  1027.       if (a->sign | b->sign) {
  1028.          x->sign = 1;
  1029.          compl1(DIG(x,0), DIG(x,0), xlen);
  1030.          }
  1031.       }
  1032.    else if (Type(*db) == T_Bignum) {   /* ior(integer,bignym) */
  1033.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1034.       alen = LEN(BigNum(&td));
  1035.       blen = LEN(BigNum(db));
  1036.       xlen = alen > blen ? alen : blen;
  1037.       if (blkreq(3 * BigNeed(blen)) == Error)
  1038.          return Error;
  1039.       a = BigNum(&td);
  1040.       b = BigNum(db);
  1041.       x = alcbignum(blen);
  1042.  
  1043.       if (alen == xlen && !a->sign)
  1044.          ad = DIG(a,0);
  1045.       else {
  1046.          tad = alcbignum(xlen);
  1047.          ad = DIG(tad,0);
  1048.          bdzero(ad, xlen - alen);
  1049.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1050.          if (a->sign)
  1051.         compl1(ad, ad, xlen);
  1052.          }
  1053.  
  1054.       if (blen == xlen && !b->sign)
  1055.          bd = DIG(b,0);
  1056.       else {
  1057.          tbd = alcbignum(xlen);
  1058.          bd = DIG(tbd,0);
  1059.          bdzero(bd, xlen - blen);
  1060.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1061.          if (b->sign)
  1062.         compl1(bd, bd, xlen);
  1063.          }
  1064.         
  1065.       for (i = 0; i < xlen; i++)
  1066.          *DIG(x,i) = ad[i] | bd[i];
  1067.  
  1068.       if (a->sign | b->sign) {
  1069.          x->sign = 1;
  1070.          compl1(DIG(x,0), DIG(x,0), xlen);
  1071.          }
  1072.       }
  1073.    /* not called for ior(integer,integer) */
  1074.  
  1075.    return mkdesc(x, dx);
  1076. }
  1077.  
  1078. /*
  1079.  *  xor(da, db) -> dx
  1080.  */
  1081.  
  1082. int bigxor(da, db, dx)
  1083. dptr da, db, dx;
  1084. {
  1085.    struct b_bignum *a, *b, *x;
  1086.    word alen, blen, xlen;
  1087.    word i;
  1088.    struct b_bignum *tad, *tbd;
  1089.    DIGIT *ad, *bd;
  1090.    struct descrip td;
  1091.    char tdigits[INTBIGBLK];
  1092.  
  1093.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  1094.       alen = LEN(BigNum(da));
  1095.       blen = LEN(BigNum(db));
  1096.       xlen = alen > blen ? alen : blen;
  1097.       if (blkreq(3 * BigNeed(xlen)) == Error)
  1098.          return Error;
  1099.       a = BigNum(da);
  1100.       b = BigNum(db);
  1101.       x = alcbignum(xlen);
  1102.  
  1103.       if (alen == xlen && !a->sign)
  1104.          ad = DIG(a,0);
  1105.       else {
  1106.          tad = alcbignum(xlen);
  1107.          ad = DIG(tad,0);
  1108.          bdzero(ad, xlen - alen);
  1109.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1110.          if (a->sign)
  1111.         compl1(ad, ad, xlen);
  1112.          }
  1113.  
  1114.       if (blen == xlen && !b->sign)
  1115.          bd = DIG(b,0);
  1116.       else {
  1117.          tbd = alcbignum(xlen);
  1118.          bd = DIG(tbd,0);
  1119.          bdzero(bd, xlen - blen);
  1120.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1121.          if (b->sign)
  1122.         compl1(bd, bd, xlen);
  1123.          }
  1124.  
  1125.       for (i = 0; i < xlen; i++)
  1126.          *DIG(x,i) = ad[i] ^ bd[i];
  1127.  
  1128.       if (a->sign ^ b->sign) {
  1129.          x->sign = 1;
  1130.          compl1(DIG(x,0), DIG(x,0), xlen);
  1131.          }
  1132.       }
  1133.    else if (Type(*da) == T_Bignum) {   /* ixor(bignum,integer) */
  1134.       itobig(IntVal(*db), (struct b_bignum *)tdigits, &td);
  1135.       alen = LEN(BigNum(da));
  1136.       blen = LEN(BigNum(&td));
  1137.       xlen = alen > blen ? alen : blen;
  1138.       if (blkreq(3 * BigNeed(alen)) == Error)
  1139.          return Error;
  1140.       a = BigNum(da);
  1141.       b = BigNum(&td);
  1142.       x = alcbignum(alen);
  1143.  
  1144.       if (alen == xlen && !a->sign)
  1145.          ad = DIG(a,0);
  1146.       else {
  1147.          tad = alcbignum(xlen);
  1148.          ad = DIG(tad,0);
  1149.          bdzero(ad, xlen - alen);
  1150.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1151.          if (a->sign)
  1152.         compl1(ad, ad, xlen);
  1153.          }
  1154.  
  1155.       if (blen == xlen && !b->sign)
  1156.          bd = DIG(b,0);
  1157.       else {
  1158.          tbd = alcbignum(xlen);
  1159.          bd = DIG(tbd,0);
  1160.          bdzero(bd, xlen - blen);
  1161.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1162.          if (b->sign)
  1163.         compl1(bd, bd, xlen);
  1164.          }
  1165.  
  1166.       for (i = 0; i < xlen; i++)
  1167.          *DIG(x,i) = ad[i] ^ bd[i];
  1168.  
  1169.       if (a->sign ^ b->sign) {
  1170.          x->sign = 1;
  1171.          compl1(DIG(x,0), DIG(x,0), xlen);
  1172.          }
  1173.       }
  1174.    else if (Type(*db) == T_Bignum) {   /* ixor(integer,bignum) */
  1175.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1176.       alen = LEN(BigNum(&td));
  1177.       blen = LEN(BigNum(db));
  1178.       xlen = alen > blen ? alen : blen;
  1179.       if (blkreq(3 * BigNeed(blen)) == Error)
  1180.          return Error;
  1181.       a = BigNum(&td);
  1182.       b = BigNum(db);
  1183.       x = alcbignum(blen);
  1184.  
  1185.       if (alen == xlen && !a->sign)
  1186.          ad = DIG(a,0);
  1187.       else {
  1188.          tad = alcbignum(xlen);
  1189.          ad = DIG(tad,0);
  1190.          bdzero(ad, xlen - alen);
  1191.          bdcopy(DIG(a,0), &ad[xlen-alen], alen);
  1192.          if (a->sign)
  1193.         compl1(ad, ad, xlen);
  1194.          }
  1195.  
  1196.       if (blen == xlen && !b->sign)
  1197.          bd = DIG(b,0);
  1198.       else {
  1199.          tbd = alcbignum(xlen);
  1200.          bd = DIG(tbd,0);
  1201.          bdzero(bd, xlen - blen);
  1202.          bdcopy(DIG(b,0), &bd[xlen-blen], blen);
  1203.          if (b->sign)
  1204.         compl1(bd, bd, xlen);
  1205.          }
  1206.  
  1207.       for (i = 0; i < xlen; i++)
  1208.          *DIG(x,i) = ad[i] ^ bd[i];
  1209.  
  1210.       if (a->sign ^ b->sign) {
  1211.          x->sign = 1;
  1212.          compl1(DIG(x,0), DIG(x,0), xlen);
  1213.          }
  1214.       }
  1215.    /* not called for ixor(integer,integer) */
  1216.  
  1217.    return mkdesc(x, dx);
  1218. }
  1219.  
  1220. /*
  1221.  *  bigshift(da, db) -> dx
  1222.  */
  1223.  
  1224. int bigshift(da, db, dx)
  1225. dptr da, db, dx;
  1226. {
  1227.    struct b_bignum *a, *x;
  1228.    word alen;
  1229.    word r = IntVal(*db) % NB;
  1230.    word q = (r >= 0 ? IntVal(*db) : (IntVal(*db) - (r += NB))) / NB;
  1231.    word xlen;
  1232.    struct b_bignum *tad;
  1233.    DIGIT *ad;
  1234.  
  1235.    if (Type(*da) == T_Bignum) {
  1236.       alen = LEN(BigNum(da));
  1237.       xlen = alen + q + 1;
  1238.       if (xlen <= 0) {
  1239.          MakeInt(0, dx);
  1240.          return Success;
  1241.          }
  1242.       else {
  1243.          if (blkreq(BigNeed(xlen) + BigNeed(alen)) == Error)
  1244.         return Error;
  1245.          a = BigNum(da);
  1246.          x = alcbignum(xlen);
  1247.          ad = DIG(a,0);
  1248.  
  1249.          if (q >= 0) {
  1250.             *DIG(x,0) = shifti1(ad, r, (DIGIT)0, DIG(x,1), alen);
  1251.             bdzero(DIG(x,alen+1), q);
  1252.             x->sign = a->sign;
  1253.             }
  1254.          else  {
  1255.             *DIG(x,0) = shifti1(ad, r, ad[alen+q] >> (NB-r), DIG(x,1), alen+q);
  1256.             }
  1257.  
  1258.          return mkdesc(x, dx);
  1259.      }
  1260.       }
  1261.    else {                              /* da is integer */
  1262.       struct descrip td;
  1263.       char tdigits[INTBIGBLK];
  1264.  
  1265.       itobig(IntVal(*da), (struct b_bignum *)tdigits, &td);
  1266.       alen = LEN(BigNum(&td));
  1267.       xlen = alen + q + 1;
  1268.       if (xlen <= 0) {
  1269.          MakeInt(0, dx);
  1270.          return Success;
  1271.          }
  1272.       else {
  1273.          if (blkreq(BigNeed(xlen) + BigNeed(alen)) == Error)
  1274.         return Error;
  1275.          a = BigNum(&td);
  1276.          x = alcbignum(xlen);
  1277.          ad = DIG(a,0);
  1278.  
  1279.          if (q >= 0) {
  1280.             *DIG(x,0) = shifti1(ad, r, (DIGIT)0, DIG(x,1), alen);
  1281.             bdzero(DIG(x,alen+1), q);
  1282.             x->sign = a->sign;
  1283.             }
  1284.          else 
  1285.             *DIG(x,0) = shifti1(ad, r, ad[alen+q] >> (NB-r), DIG(x,1), alen+q);
  1286.  
  1287.          return mkdesc(x, dx);
  1288.          }
  1289.       }
  1290. }
  1291.  
  1292. /*
  1293.  *  negative if da < db
  1294.  *  zero if da == db
  1295.  *  positive if da > db
  1296.  */
  1297.  
  1298. word bigcmp(da, db)
  1299. dptr da, db;
  1300. {
  1301.    struct b_bignum *a = BigNum(da);
  1302.    struct b_bignum *b = BigNum(db);
  1303.    word alen, blen; 
  1304.  
  1305.    if (Type(*da) == T_Bignum && Type(*db) == T_Bignum) {
  1306.       if (a->sign != b->sign)
  1307.          return (b->sign - a->sign);
  1308.       alen = LEN(a);
  1309.       blen = LEN(b);
  1310.       if (alen != blen)
  1311.          return (a->sign ? blen - alen : alen - blen);
  1312.  
  1313.       if (a->sign)
  1314.          return cmp1(DIG(b,0), DIG(a,0), alen);
  1315.       else
  1316.          return cmp1(DIG(a,0), DIG(b,0), alen);
  1317.       }
  1318.    else if (Type(*da) == T_Bignum)    /* cmp(bignum, integer) */
  1319.       return bigcmpi(da, IntVal(*db));
  1320.    else                               /* cmp(integer, bignum) */
  1321.       return -bigcmpi(db, IntVal(*da));
  1322. }
  1323.  
  1324. /*
  1325.  *  ?da -> dx
  1326.  */  
  1327.  
  1328. int bigrand(da, dx)
  1329. dptr da, dx;
  1330. {
  1331.    struct b_bignum *a;
  1332.    word alen = LEN(BigNum(da));
  1333.    struct b_bignum *x;
  1334.    struct b_bignum *td;
  1335.    DIGIT *d;
  1336.    word i;
  1337.    double rval;
  1338.  
  1339.    if (blkreq(4 * BigNeed(alen + 1) + 4) == Error)
  1340.       return Error;
  1341.    x = alcbignum(alen);
  1342.    td = alcbignum(alen + 1);
  1343.    d = DIG(td,0);
  1344.    a = BigNum(da);
  1345.  
  1346.    for (i = alen; i >= 0; i--) {
  1347.       rval = RandVal;
  1348.       d[i] = rval * B;
  1349.       }
  1350.     
  1351.    div1(d, DIG(a,0), NULL, DIG(x,0), (word)1, alen);
  1352.    addi1(DIG(x,0), (word)1, DIG(x,0), alen);
  1353.    return mkdesc(x, dx);
  1354. }
  1355.  
  1356. /*
  1357.  *  da + i -> dx
  1358.  */
  1359.  
  1360. static int bigaddi(da, i, dx)
  1361. dptr da, dx;
  1362. word i;
  1363. {
  1364.    struct b_bignum *a, *x; 
  1365.    word alen; 
  1366.  
  1367.    if (i < 0)
  1368.       return bigsubi(da, -i, dx);
  1369.    else if (i != (DIGIT)i) {
  1370.       struct descrip td;
  1371.       char tdigits[INTBIGBLK];
  1372.  
  1373.       itobig(i, (struct b_bignum *)tdigits, &td);
  1374.       return bigadd(da, &td, dx);
  1375.       }
  1376.    else {
  1377.       alen = LEN(BigNum(da));
  1378.       if (blkreq(BigNeed(alen + 1)) == Error)
  1379.          return Error;
  1380.       a = BigNum(da);
  1381.       if (a->sign) {
  1382.      x = alcbignum(alen);
  1383.          subi1(DIG(a,0), i, DIG(x,0), alen);
  1384.          }
  1385.       else {
  1386.          x = alcbignum(alen + 1);
  1387.          *DIG(x,0) = addi1(DIG(a,0), i, DIG(x,1), alen);
  1388.          }
  1389.       x->sign = a->sign;
  1390.       return mkdesc(x, dx);
  1391.       }
  1392. }
  1393.  
  1394. /*
  1395.  *  da - i -> dx
  1396.  */
  1397.  
  1398. static int bigsubi(da, i, dx)
  1399. dptr da, dx;
  1400. word i;
  1401. {
  1402.    struct b_bignum *a, *x; 
  1403.    word alen;
  1404.  
  1405.    if (i < 0)
  1406.       return bigaddi(da, -i, dx);
  1407.    else if (i != (DIGIT)i) {
  1408.       struct descrip td;
  1409.       char tdigits[INTBIGBLK];
  1410.  
  1411.       itobig(i, (struct b_bignum *)tdigits, &td);
  1412.       return bigsub(da, &td, dx);
  1413.       }
  1414.    else {
  1415.       alen = LEN(BigNum(da));
  1416.       if (blkreq(BigNeed(alen + 1)) == Error)
  1417.      return Error;
  1418.       a = BigNum(da);
  1419.       if (a->sign) {
  1420.          x = alcbignum(alen + 1);
  1421.          *DIG(x,0) = addi1(DIG(a,0), i, DIG(x,1), alen);
  1422.          }
  1423.       else {
  1424.          x = alcbignum(alen);
  1425.          subi1(DIG(a,0), i, DIG(x,0), alen);
  1426.          }
  1427.       x->sign = a->sign;
  1428.       return mkdesc(x, dx);
  1429.       }
  1430. }
  1431.  
  1432. /*
  1433.  *  da * i -> dx
  1434.  */
  1435.  
  1436. static int bigmuli(da, i, dx)
  1437. dptr da, dx;
  1438. word i;
  1439. {
  1440.    struct b_bignum *a, *x; 
  1441.    word alen;
  1442.  
  1443.    if (i <= -B || i >= B) {
  1444.       struct descrip td;
  1445.       char tdigits[INTBIGBLK];
  1446.  
  1447.       itobig(i, (struct b_bignum *)tdigits, &td);
  1448.       return bigmul(da, &td, dx);
  1449.       }
  1450.    else {
  1451.       alen = LEN(BigNum(da));
  1452.       if (blkreq(BigNeed(alen + 1)) == Error)
  1453.      return Error;
  1454.       a = BigNum(da);
  1455.       x = alcbignum(alen + 1);
  1456.       if (i >= 0)
  1457.          x->sign = a->sign;
  1458.       else {
  1459.          x->sign = 1 ^ a->sign;
  1460.          i = -i;
  1461.          }
  1462.       *DIG(x,0) = muli1(DIG(a,0), i, 0, DIG(x,1), alen);
  1463.       return mkdesc(x, dx);
  1464.       }
  1465. }
  1466.  
  1467. /*
  1468.  *  da / i -> dx
  1469.  */
  1470.  
  1471. static int bigdivi(da, i, dx)
  1472. dptr da, dx;
  1473. word i;
  1474. {
  1475.    struct b_bignum *a, *x; 
  1476.    word alen;
  1477.  
  1478.    if (i <= -B || i >= B) {
  1479.       struct descrip td;
  1480.       char tdigits[INTBIGBLK];
  1481.  
  1482.       itobig(i, (struct b_bignum *)tdigits, &td);
  1483.       return bigdiv(da, &td, dx);
  1484.       }
  1485.    else {
  1486.       alen = LEN(BigNum(da));
  1487.       if (blkreq(BigNeed(alen)) == Error)
  1488.      return Error;
  1489.       a = BigNum(da);
  1490.       x = alcbignum(alen);
  1491.       if (i >= 0)
  1492.          x->sign = a->sign;
  1493.       else {
  1494.          x->sign = 1 ^ a->sign;
  1495.          i = -i;
  1496.          }
  1497.       divi1(DIG(a,0), i, DIG(x,0), alen);
  1498.       return mkdesc(x, dx);
  1499.       }
  1500. }
  1501.  
  1502. /*
  1503.  *  da % i -> dx
  1504.  */
  1505.  
  1506. static int bigmodi(da, i, dx)
  1507. dptr da, dx;
  1508. word i;
  1509. {
  1510.    struct b_bignum *a, *temp;
  1511.    word alen;
  1512.    word x;
  1513.  
  1514.    if (i <= -B || i >= B) {
  1515.       struct descrip td;
  1516.       char tdigits[INTBIGBLK];
  1517.  
  1518.       itobig(i, (struct b_bignum *)tdigits, &td);
  1519.       return bigmod(da, &td, dx);
  1520.       }
  1521.    else {
  1522.       alen = LEN(BigNum(da));
  1523.       if (blkreq(BigNeed(alen)) == Error)
  1524.      return Error;
  1525.       a = BigNum(da);
  1526.       temp = alcbignum(alen);
  1527.       x = divi1(DIG(a,0), Abs(i), DIG(temp,0), alen);
  1528.       if (a->sign)
  1529.      x = -x;
  1530.       MakeInt(x, dx);
  1531.       return Success;
  1532.       }
  1533. }
  1534.  
  1535. /*
  1536.  *  da ^ i -> dx
  1537.  */
  1538.  
  1539. static int bigpowi(da, i, dx)
  1540. dptr da, dx;
  1541. word i;
  1542. {
  1543.    int n = WordBits;
  1544.  
  1545.    if (i > 0) {
  1546.       /* scan bits left to right.  skip leading 1. */
  1547.       while (--n >= 0)
  1548.          if (i & ((word)1 << n))
  1549.         break;
  1550.       /* then, for each zero, square the partial result;
  1551.          for each one, square it and multiply it by a */
  1552.       *dx = *da;
  1553.       while (--n >= 0) {
  1554.          if (bigmul(dx, dx, dx) == Error)
  1555.         return Error;
  1556.          if (i & ((word)1 << n))
  1557.             if (bigmul(dx, da, dx) == Error)
  1558.            return Error;
  1559.          }
  1560.       }
  1561.    else {
  1562.       MakeInt(0, dx);
  1563.       }
  1564.    return Success;
  1565. }
  1566.  
  1567. /*
  1568.  *  a ^ i -> dx
  1569.  */
  1570.  
  1571. static int bigpowii(a, i, dx)
  1572. word a, i;
  1573. dptr dx;
  1574. {
  1575.    word x, y;
  1576.    int n = WordBits;
  1577.    int isbig = 0;
  1578.  
  1579.    if (a == 0 || i <= 0) {              /* special cases */
  1580.       if (a == 0 && i <= 0)             /* 0 ^ negative -> error */
  1581.          RetError(-204, nulldesc);
  1582.       if (a == -1) {                    /* -1 ^ [odd,even] -> [-1,+1] */
  1583.          if (!(i & 1))
  1584.         a = 1;
  1585.          }
  1586.       else if (a != 1) {                /* 1 ^ any -> 1 */
  1587.          a = 0;
  1588.          }                   /* others ^ negative -> 0 */
  1589.       MakeInt(a, dx);
  1590.       }
  1591.    else {
  1592.       struct descrip td;
  1593.       char tdigits[INTBIGBLK];
  1594.  
  1595.       /* scan bits left to right.  skip leading 1. */
  1596.       while (--n >= 0)
  1597.          if (i & ((word)1 << n))
  1598.         break;
  1599.       /* then, for each zero, square the partial result;
  1600.          for each one, square it and multiply it by a */
  1601.       x = a;
  1602.       while (--n >= 0) {
  1603.          if (isbig) {
  1604.             if (bigmul(dx, dx, dx) == Error)
  1605.            return Error;
  1606.         }
  1607.          else {
  1608.             y = mul(x, x);
  1609.             if (!over_flow)
  1610.                x = y;
  1611.             else {
  1612.                itobig(x, (struct b_bignum *)tdigits, &td);
  1613.                if (bigmul(&td, &td, dx) == Error)
  1614.                  return Error;
  1615.                isbig = (Type(*dx) == T_Bignum);
  1616.                } 
  1617.             }
  1618.          if (i & ((word)1 << n)) {
  1619.             if (isbig) {
  1620.                if (bigmuli(dx, a, dx) == Error)
  1621.           return Error;
  1622.            }
  1623.             else {
  1624.                y = mul(x, a);
  1625.                if (!over_flow)
  1626.                   x = y;
  1627.                else {
  1628.                   itobig(x, (struct b_bignum *)tdigits, &td);
  1629.                   if (bigmuli(&td, a, dx) == Error)
  1630.              return Error;
  1631.                   isbig = (Type(*dx) == T_Bignum);
  1632.                   }
  1633.                }
  1634.             }
  1635.          }
  1636.       if (!isbig) {
  1637.      MakeInt(x, dx);
  1638.      }
  1639.       }
  1640.    return Success;
  1641. }
  1642.  
  1643. /*
  1644.  *  negative if da < i
  1645.  *  zero if da == i
  1646.  *  positive if da > i
  1647.  */  
  1648.   
  1649. static word bigcmpi(da, i)
  1650. dptr da;
  1651. word i;
  1652. {
  1653.    struct b_bignum *a = BigNum(da);
  1654.    word alen = LEN(a);
  1655.  
  1656.    if (i > -B && i < B) {
  1657.       if (i >= 0)
  1658.          if (a->sign)
  1659.         return -1;
  1660.          else
  1661.         return cmpi1(DIG(a,0), i, alen);
  1662.       else
  1663.          if (a->sign)
  1664.         return -cmpi1(DIG(a,0), -i, alen);
  1665.          else
  1666.         return 1;
  1667.       }
  1668.    else {
  1669.       struct descrip td;
  1670.       char tdigits[INTBIGBLK];
  1671.  
  1672.       itobig(i, (struct b_bignum *)tdigits, &td);
  1673.       return bigcmp(da, &td);
  1674.       }
  1675. }
  1676.  
  1677.  
  1678. /* These are all straight out of Knuth vol. 2, Sec. 4.3.1. */
  1679.  
  1680. /*
  1681.  *  (u,n) + (v,n) -> (w,n)
  1682.  *
  1683.  *  returns carry, 0 or 1
  1684.  */
  1685.  
  1686. static DIGIT add1(u, v, w, n)
  1687. DIGIT *u, *v, *w;
  1688. word n;
  1689. {
  1690.    uword dig, carry; 
  1691.    word i;
  1692.  
  1693.    carry = 0;
  1694.    for (i = n; --i >= 0; ) {
  1695.       dig = (uword)u[i] + v[i] + carry;
  1696.       w[i] = lo(dig);
  1697.       carry = hi(dig);
  1698.       }
  1699.    return carry;
  1700. }
  1701.  
  1702. /*
  1703.  *  (u,n) - (v,n) -> (w,n)
  1704.  *
  1705.  *  returns carry, 0 or -1
  1706.  */
  1707.  
  1708. static word sub1(u, v, w, n)
  1709. DIGIT *u, *v, *w;
  1710. word n;
  1711. {
  1712.    uword dig, carry; 
  1713.    word i;
  1714.  
  1715.    carry = 0;
  1716.    for (i = n; --i >= 0; ) {
  1717.       dig = (uword)u[i] - v[i] + carry;
  1718.       w[i] = lo(dig);
  1719.       carry = signed_hi(dig);
  1720.       }
  1721.    return carry;
  1722. }
  1723.  
  1724. /*
  1725.  *  (u,n) * (v,m) -> (w,m+n)
  1726.  */
  1727.  
  1728. static novalue mul1(u, v, w, n, m)
  1729. DIGIT *u, *v, *w;
  1730. word n, m;
  1731. {
  1732.    word i, j;
  1733.    uword dig, carry;
  1734.  
  1735.    bdzero(&w[m], n);
  1736.  
  1737.    for (j = m; --j >= 0; ) {
  1738.       carry = 0;
  1739.       for (i = n; --i >= 0; ) {
  1740.          dig = (uword)u[i] * v[j] + w[i+j+1] + carry;
  1741.          w[i+j+1] = lo(dig);
  1742.          carry = hi(dig);
  1743.          }
  1744.       w[j] = carry;
  1745.       }
  1746. }
  1747.  
  1748. /*
  1749.  *  (a,m+n) / (b,n) -> (q,m+1) (r,n)
  1750.  *
  1751.  *  if q or r is NULL, the quotient or remainder is discarded
  1752.  */
  1753.  
  1754. static novalue div1(a, b, q, r, m, n)
  1755. DIGIT *a, *b, *q, *r;
  1756. word m, n;
  1757. {
  1758.    uword qhat, rhat;
  1759.    uword dig, carry;
  1760.    struct b_bignum *tu, *tv;
  1761.    DIGIT *u, *v;
  1762.    word d;
  1763.    word i, j;
  1764.  
  1765.    /* blkreq's done in calling routines */
  1766.  
  1767.    tu = alcbignum(m + n + 1);
  1768.    tv = alcbignum(n);
  1769.    u = DIG(tu,0);
  1770.    v = DIG(tv,0);
  1771.  
  1772.    /* D1 */
  1773.    for (d = 0; d < NB; d++)
  1774.       if (b[0] & (1 << (NB - 1 - d)))
  1775.          break;
  1776.  
  1777.    u[0] = shifti1(a, d, (DIGIT)0, &u[1], m+n);
  1778.    shifti1(b, d, (DIGIT)0, v, n);
  1779.  
  1780.    /* D2, D7 */
  1781.    for (j = 0; j <= m; j++) {
  1782.       /* D3 */
  1783.       if (u[j] == v[0]) {
  1784.          qhat = B - 1;
  1785.          rhat = (uword)v[0] + u[j+1];
  1786.          }
  1787.       else {
  1788.          uword numerator = dbl(u[j], u[j+1]);
  1789.          qhat = numerator / (uword)v[0];
  1790.          rhat = numerator % (uword)v[0];
  1791.          }
  1792.  
  1793.       while (rhat < B && qhat * v[1] > dbl(rhat, u[j+2])) {
  1794.          qhat -= 1;
  1795.          rhat += v[0];
  1796.          }
  1797.             
  1798.       /* D4 */
  1799.       carry = 0;
  1800.       for (i = n; i > 0; i--) {
  1801.          dig = u[i+j] - v[i-1] * qhat + carry;       /* -BSQ+B .. B-1 */
  1802.          u[i+j] = lo(dig);
  1803.          if ((uword)dig < B)
  1804.             carry = hi(dig);
  1805.          else carry = hi(dig) | -B;
  1806.          }
  1807.       carry = (word)(carry + u[j]) < 0;
  1808.  
  1809.       /* D5 */
  1810.       if (q)
  1811.      q[j] = qhat;
  1812.  
  1813.       /* D6 */
  1814.       if (carry) {
  1815.          if (q)
  1816.         q[j] -= 1;
  1817.          carry = 0;
  1818.          for (i = n; i > 0; i--) {
  1819.             dig = (uword)u[i+j] + v[i-1] + carry;
  1820.             u[i+j] = lo(dig);
  1821.             carry = hi(dig);
  1822.             }
  1823.          }
  1824.       }
  1825.  
  1826.    if (r) {
  1827.       if (d == 0)
  1828.          shifti1(&u[m+1], (word)d, (DIGIT)0, r, n);
  1829.       else
  1830.          r[0] = shifti1(&u[m+1], (word)(NB - d), u[m+n]>>d, &r[1], n - 1);
  1831.       }
  1832. }
  1833.  
  1834. /*
  1835.  *  - (u,n) -> (w,n)
  1836.  *
  1837.  */
  1838.  
  1839. static novalue compl1(u, w, n)
  1840. DIGIT *u, *w;
  1841. word n;
  1842. {
  1843.    uword dig, carry = 0;
  1844.    word i;
  1845.  
  1846.    for (i = n; --i >= 0; ) {
  1847.       dig = carry - u[i];
  1848.       w[i] = lo(dig);
  1849.       carry = signed_hi(dig);
  1850.       }
  1851. }
  1852.  
  1853. /*
  1854.  *  (u,n) : (v,n)
  1855.  */
  1856.  
  1857. static word cmp1(u, v, n)
  1858. DIGIT *u, *v;
  1859. word n;
  1860. {
  1861.    word i;
  1862.  
  1863.    for (i = 0; i < n; i++)
  1864.       if (u[i] != v[i])
  1865.          return u[i] > v[i] ? 1 : -1;
  1866.    return 0;
  1867. }
  1868.  
  1869. /*
  1870.  *  (u,n) + k -> (w,n)
  1871.  *
  1872.  *  k in 0 .. B-1
  1873.  *  returns carry, 0 or 1
  1874.  */
  1875.  
  1876. static DIGIT addi1(u, k, w, n)
  1877. DIGIT *u, *w;
  1878. word k;
  1879. word n;
  1880. {
  1881.    uword dig, carry;
  1882.    word i;
  1883.     
  1884.    carry = k;
  1885.    for (i = n; --i >= 0; ) {
  1886.       dig = (uword)u[i] + carry;
  1887.       w[i] = lo(dig);
  1888.       carry = hi(dig);
  1889.       }
  1890.    return carry;
  1891. }
  1892.  
  1893. /*
  1894.  *  (u,n) - k -> (w,n)
  1895.  *
  1896.  *  k in 0 .. B-1
  1897.  *  u must be greater than k
  1898.  */
  1899.  
  1900. static novalue subi1(u, k, w, n)
  1901. DIGIT *u, *w;
  1902. word k;
  1903. word n;
  1904. {
  1905.    uword dig, carry;
  1906.    word i;
  1907.     
  1908.    carry = -k;
  1909.    for (i = n; --i >= 0; ) {
  1910.       dig = (uword)u[i] + carry;
  1911.       w[i] = lo(dig);
  1912.       carry = signed_hi(dig);
  1913.       }
  1914. }
  1915.  
  1916. /*
  1917.  *  (u,n) * k + c -> (w,n)
  1918.  *
  1919.  *  k in 0 .. B-1
  1920.  *  returns carry, 0 .. B-1
  1921.  */
  1922.  
  1923. static DIGIT muli1(u, k, c, w, n)
  1924. DIGIT *u, *w;
  1925. word k;
  1926. int c;
  1927. word n;
  1928. {
  1929.    uword dig, carry;
  1930.    word i;
  1931.  
  1932.    carry = c;
  1933.    for (i = n; --i >= 0; ) {
  1934.       dig = (uword)k * u[i] + carry;
  1935.       w[i] = lo(dig);
  1936.       carry = hi(dig);
  1937.       }
  1938.    return carry;
  1939. }
  1940.  
  1941. /*
  1942.  *  (u,n) / k -> (w,n)
  1943.  *
  1944.  *  k in 0 .. B-1
  1945.  *  returns remainder, 0 .. B-1
  1946.  */
  1947.  
  1948. static DIGIT divi1(u, k, w, n)
  1949. DIGIT *u, *w;
  1950. word k;
  1951. word n;
  1952. {
  1953.    uword dig, remain;
  1954.    word i;
  1955.  
  1956.    remain = 0;
  1957.    for (i = 0; i < n; i++) {
  1958.       dig = dbl(remain, u[i]);
  1959.       w[i] = dig / k;
  1960.       remain = dig % k;
  1961.       }
  1962.    return remain;
  1963. }
  1964.  
  1965. /*
  1966.  *  ((u,n) << k) + c -> (w,n)
  1967.  *
  1968.  *  k in 0 .. NB-1
  1969.  *  c in 0 .. B-1 
  1970.  *  returns carry, 0 .. B-1
  1971.  */
  1972.  
  1973. static DIGIT shifti1(u, k, c, w, n)
  1974. DIGIT *u, c, *w;
  1975. word k;
  1976. word n;
  1977. {
  1978.    uword dig;
  1979.    word i;
  1980.  
  1981.    if (k == 0) {
  1982.       bdcopy(u, w, n);
  1983.       return 0;
  1984.       }
  1985.     
  1986.    for (i = n; --i >= 0; ) {
  1987.       dig = ((uword)u[i] << k) + c;
  1988.       w[i] = lo(dig);
  1989.       c = hi(dig);
  1990.       }
  1991.    return c;
  1992. }
  1993.  
  1994. /*
  1995.  *  (u,n) : k
  1996.  *
  1997.  *  k in 0 .. B-1
  1998.  */
  1999.  
  2000. static word cmpi1(u, k, n)
  2001. DIGIT *u;
  2002. word k;
  2003. word n;
  2004. {
  2005.    word i;
  2006.  
  2007.    for (i = 0; i < n-1; i++)
  2008.       if (u[i])
  2009.      return 1;
  2010.    if (u[n - 1] == (DIGIT)k)
  2011.       return 0;
  2012.    return u[n - 1] > (DIGIT)k ? 1 : -1;
  2013. }
  2014.  
  2015. static novalue bdzero(dest, l)
  2016. DIGIT *dest;
  2017. word l;
  2018. {
  2019.    word i;
  2020.  
  2021.    for (i = 0; i < l; i++)
  2022.       dest[i] = 0;
  2023. }
  2024.  
  2025. static novalue bdcopy(src, dest, l)
  2026. DIGIT *src, *dest;
  2027. word l;
  2028. {
  2029.    word i;
  2030.  
  2031.    for (i = 0; i < l; i++)
  2032.       dest[i] = src[i];
  2033. }
  2034. #else                    /* LargeInts */
  2035. static char x;            /* prevent empty module */
  2036. #endif                    /* LargeInts */
  2037.